Descomposición LU y Métodos de Gauss-Seidel (página 2)

PASOS
PARA ENCONTRAR LA MATRIZ
TRIANGULAR INFERIOR (MATRIZ [L])

Para encontrar la matriz triangular inferior se busca
hacer ceros los valores de
arriba de cada pivote, así como también convertir
en 1 cada pivote. Se utiliza el mismo concepto de
"factor" explicado anteriormente y se ubican todos los "factores"
debajo de la diagonal según corresponda en cada
uno.

Esquemáticamente se busca lo
siguiente:

Originalmente se tenía:

Debido a que [A] = [L][U], al encontrar [L] y [U] a
partir de [A] no se altera en nada la ecuación y se tiene
lo siguiente:

Por lo tanto, si Ax = b, entonces LUx = b, de manera que
Ax = LUx = b.

PASOS PARA RESOLVER UN SISTEMA DE
ECUACIONES POR
EL MÉTODO DE DESCOMPOSICIÓN LU

1. Obtener la matriz triangular inferior L y la matriz
   triangular superior U.
2. Resolver Ly = b (para encontrar y).
3. El resultado del paso anterior se guarda en una
   matriz nueva de nombre "y".
4. Realizar Ux = y (para encontrar x).
5. El resultado del paso anterior se almacena en una
   matriz nueva llamada "x", la cual brinda los valores
   correspondientes a las incógnitas de la
   ecuación.

EJEMPLO 1 DE DESCOMPOSICIÓN
LU

PROBLEMA: Encontrar los valores de
x1, x2 y x3 para el siguiente
sistema de ecuaciones:

NOTA: Recuérdese que si la matriz es 2×2
se hará 1 iteración; si es 3×3, 2 iteraciones; si
es 4×4, 3 iteraciones; y así sucesivamente.

SOLUCIÓN:

ITERACIÓN
1

factor 1 = (a21 / a11) = 5 / 4 =
1.25

factor 2 = (a31 / a11) = 1 / 4 =
0.25

Encontrando [U]

fila 2 = – (factor 1) * (fila 1) + (fila 2)

fila 3 = – (factor 2) * (fila 1) + (fila 3)

a11 = a11

a12 = a12

a13 = a13

a21 = – (1.25) * (4) + (5) = 0

a22 = – (1.25) * (- 2) + (1) = 3.5

a23 = – (1.25) + (- 1) + (- 1) =
0.25

a31 = – (0.25) * (4) + (1) = 0

a32 = – (0.25) * (- 2) + (2) = 2.5

a33 = – (0.25) * (- 1) + (- 1) = –
0.75

Encontrando [L]

ITERACIÓN
2

factor 3 = (u32 / u22) = 2.5 / 3.5
= 0.7142857143

Encontrando [U]

fila 3 = – (factor 3) * (fila 2) + (fila 3)

a31 = – (2.5 / 3.5) * (0) + (0) =
0

a32 = – (2.5 / 3.5) * (3.5) + (2.5) =
0

a33 = – (2.5 / 3.5) * (0.25) + (- 0.75) = –
0.9285714286

Encontrando [L]

Ahora ya se tiene la matriz [U] y la matriz [L]. El
siguiente paso es resolver

Ly = b para encontrar la matriz y. En pocas palabras es
como que se pidiera resolver el siguiente sistema de ecuaciones,
encontrando los valores de y1, y2 y
y3:

Al resolver el sistema anterior, se obtienen los
siguientes valores para y1, y2 y
y3:

El último paso es resolver Ux = y para encontrar
la matriz x. En otras palabras es como que se pidiera resolver el
siguiente sistema de ecuaciones, encontrando los valores de
x1, x2 y x3:

La solución del sistema es:

Este es finalmente el valor de x1,
x2 y x3; es decir, la respuesta del ejercicio utilizando la
descomposición LU.

EJEMPLO 2 DE DESCOMPOSICIÓN
LU

PROBLEMA: Encontrar los valores de
x1, x2 y x3 para el siguiente
sistema de ecuaciones:

SOLUCIÓN:

ITERACIÓN
1

factor 1 = (a21 / a11) = 5/11 =
0.4545454545

factor 2 = (a31 / a11) = 4/11 =
0.3636363636

Encontrando [U]

fila 2 = – (factor 1) * (fila 1) + (fila 2)

fila 3 = – (factor 2) * (fila 1) + (fila 3)

a11 = a11

a12 = a12

a13 = a13

a21 = – (0.4545454545) * (11) + (5) =
0

a22 = – (0.4545454545) * (- 3) + (- 2) = –
0.6363636365

a23 = – (0.4545454545) + (- 2) + (- 8) = –
7.0909090919

a31 = – (0.3636363636) * (11) + (4) =
0

a32 = – (0.3636363636) * (- 3) + (- 7) = –
5.909090909

a33 = – (0.3636363636) * (- 2) + (2) =
2.7272727272

Encontrando [L]

ITERACIÓN
2

factor 3 = (u32/u22) = – 5.909090909 / – 0.6363636365 =
9.285714284

Encontrando [U]

fila 3 = – (factor 3) * (fila 2) + (fila 3)

a31 = – (9.285714284) * (0) + (0) =
0

a32 = – (9.285714284) * (- 0.6363636365) + (-
5.909090909) = 0

a33 = – (9.285714284) * (- 7.0909090919) +
(2.7272727272) = 68.57142857

Encontrando [L]

Ahora ya se tiene la matriz [U] y la matriz [L]. El
siguiente paso es resolver

Ly = b para encontrar la matriz y. En pocas palabras es
como que se pidiera resolver el siguiente sistema de ecuaciones,
encontrando los valores de y1, y2 y
y3:

Al resolver el sistema anterior, se obtienen los
siguientes valores para y1, y2 y
y3:

El último paso es resolver Ux = y para encontrar
la matriz x. En otras palabras es como que se pidiera resolver el
siguiente sistema de ecuaciones, encontrando los valores de
x1, x2 y x3:

La solución del sistema es:

Este es finalmente el valor de x1, x2 y x3; es decir, la
respuesta del ejercicio utilizando la descomposición
LU.

MÉTODO DE
GAUSS-SEIDEL

El método de
Gauss-Seidel es un método iterativo y por lo mismo resulta
ser bastante eficiente. Se comienza planteando el sistema de
ecuaciones con el que se va a trabajar:

De la ecuación 1 despejar x1, de la
ecuación 2 despejar x2, …, de la
ecuación n despejar xn. Esto da el
siguiente conjunto de ecuaciones:

Este último conjunto de ecuaciones son las que
forman las fórmulas iterativas con las que se va a estar
trabajando. Para comenzar el proceso
iterativo, se le da el valor de cero a las variables
x2,…, xn; esto dará un primer
valor para x1. Más precisamente, se tiene
que:

Enseguida, se sustituye este valor de x1 en
la ecuación 2, y las variables x3,…,
xn siguen teniendo el valor de cero. Esto da el
siguiente valor para x2:

Estos últimos valores de x1 y
x2, se sustituyen en la ecuación 3, mientras
que x4,…, xn siguen teniendo el
valor de cero; y así sucesivamente hasta llegar a la
última ecuación. Todo este paso arrojará una
lista de primeros valores para las incógnitas, la cual
conforma el primer paso en el proceso iterativo. Para una mejor
comprensión esto se simbolizará de esta
forma:

Se vuelve a repetir el proceso, pero ahora sustituyendo
estos últimos datos en vez de
ceros como al inicio. Se obtendrá una segunda lista de
valores para cada una de las incógnitas, lo cual se
simbolizará así:

En este momento se pueden calcular los errores
aproximados relativos, respecto a cada una de las
incógnitas. La lista de errores se presenta a
continuación:

El proceso se vuelve a repetir hasta que:

donde se
debe prefijar convenientemente.

EJEMPLO 1 DEL MÉTODO DE
GAUSS-SEIDEL

PROBLEMA: Usar el método de
Gauss-Seidel para aproximar la solución del
sistema:

hasta que

SOLUCIÓN:

Primero se despejan las incógnitas x1,
x2 y x3 de las ecuaciones 1, 2 y 3
respectivamente. Se tiene:

Estas últimas son el juego de
fórmulas iterativas que se estará
utilizando.

Se comienza el proceso iterativo sustituyendo los
valores de x2 = x3 = 0 en la primera
ecuación, para calcular el valor de
x1:

Ahora se sustituye y x3 = 0 en la segunda ecuación
para obtener x2:

Ahora se sustituye y en
la tercera ecuación para obtener x3:

Así se tiene la primera aproximación a la
solución del sistema:

Puesto que todavía no se puede calcular
ningún error aproximado, se repite el proceso pero ahora
con los últimos datos obtenidos para las
incógnitas:

Sustituyendo y en la
ecuación 1 se obtiene Sustituyendo y en
la ecuación 2 se obtiene finalmente, sustituyendo y en la ecuación 3 se obtiene
. Es así
como se tiene la segunda lista de valores de aproximación
a la solución del sistema:

Ahora se pueden calcular los errores absolutos para cada
una de las incógnitas:

Puesto que no se ha logrado el objetivo, se
debe repetir el mismo proceso con los últimos valores
obtenidos de cada una de las incógnitas. Nótese que
aunque el error aproximado ya cumple con ser menor al 1%, esto se debe cumplir
para los tres errores aproximados. Por lo tanto se repite el
mismo proceso. Omitiendo los pasos intermedios, se
obtiene:

En este caso se tienen los siguientes errores
aproximados:

Se puede observar que ahora se ha cumplido el objetivo
para cada uno de los errores aproximados. Por lo tanto, se
concluye que la solución aproximada es:

Importante observación respecto al método de
Gauss-Seidel: Es lógico preguntarse si siempre el
método de Gauss-Seidel converge a la solución del
sistema de ecuaciones y también es lógico esperar
que la respuesta es NO.

Un resultado de Análisis numérico da una
condición suficiente para la convergencia del
método.

Teorema: El método de Gauss-Seidel
converge a la solución del sistema si se cumple la
condición de que la matriz de coeficientes del sistema sea
una matriz diagonalmente dominante, es decir, si se cumple
la siguiente condición:

La condición de ser una matriz diagonalmente
dominante simplemente significa que los elementos de la diagonal
son mayores (en valor absoluto) que la suma de los valores
absolutos de los demás elementos del mismo renglón.
Nótese que en el ejemplo anterior, la matriz sí es
diagonalmente dominante y por lo tanto, el método de
Gauss-Seidel sí converge a la solución del
sistema.

Sin embargo, la condición de la matriz
diagonalmente dominante, solamente es una condición
suficiente pero no necesaria, es decir, existen sistemas de
ecuaciones que no cumplen con la condición y que sí
convergen a la solución y también existen sistemas
de ecuaciones que no cumplen con la condición y que no
convergen a la solución.

Finalmente, obsérvese que aunque un sistema no
cumpla con la condición de ser diagonalmente dominante, es
posible a veces, lograr que sí se cumpla con esta
condición mediante un intercambio de renglones, como se
verá en el siguiente ejemplo:

EJEMPLO 2 DEL MÉTODO DE
GAUSS-SEIDEL

PROBLEMA: Usar el método de
Gauss-Seidel para aproximar la solución del
sistema:

hasta que

SOLUCIÓN:

En este caso se puede observar que el sistema no es
diagonalmente dominante, lo cual se comprueba con los siguientes
cálculos:

Primera fila:

|a11| > (|a12| +
|a13|)

5 > (1.4 + 2.7)

5 > 4.1; es cierto.

La condición se cumple para la primera
fila.

Segunda fila:

|a22| > (|a21| +
|a23|)

2.5 > (0.7 + 15)

2.5 > 15.7; no es cierto.

La condición no se cumple para la segunda
fila.

|a33| > (|a31| +
|a32|)

4.4 > (3.3 + 11)

4.4 > 14.3; no es cierto.

La condición no se cumple para la tercera
fila.

Para que el sistema sea diagonalmente dominante, la
condición debe cumplirse para todas las filas. Por lo
tanto, el sistema anterior no es diagonalmente
dominante.

NOTA: Recuérdese que la diagonal principal
está compuesta por a11, a22 y
a33.

Sin embargo, al hacer el intercambio del renglón
2 por el renglón 3, se tiene el siguiente
sistema:

En este caso se puede observar que el sistema sí
es diagonalmente dominante, lo cual se comprueba con los
siguientes cálculos:

Primera fila:

|a11| > (|a12| +
|a13|)

5 > (1.4 + 2.7)

5 > 4.1; es cierto.

La condición se cumple para la primera
fila.

Segunda fila:

|a22| > (|a21| +
|a23|)

11 > (3.3 + 4.4)

11 > 7.7; es cierto.

La condición se cumple para la segunda
fila.

|a33| > (|a31| +
|a32|)

15 > (0.7 + 2.5)

15 > 3.2; es cierto.

La condición se cumple para la tercera
fila.

Para que el sistema sea diagonalmente dominante, la
condición debe cumplirse para todas las filas. En este
caso efectivamente la condición se cumple para todas las
filas, por lo cual el sistema anterior es diagonalmente
dominante. Por lo tanto se procede a despejar x1,
x2 y x3 de las ecuaciones 1, 2 y 3
respectivamente:

Se comienza el proceso iterativo sustituyendo los
valores de x2 = 0 x3 = 0 en la
ecuación 1 para obtener x1:

Ahora se sustituye x1 = -18.84 y
x3 = 0 en la ecuación 2 para obtener
x2:

Por lo tanto los valores obtenidos en la primera
iteración son:

Puesto que sólo se tiene la primera
aproximación de la solución del sistema, se debe
seguir avanzando en el proceso iterativo. Sustituyendo x2 =
-3.152 y x3 = -0.04613 en la ecuación 1, se obtiene x1 =
-19.69765; sustituyendo x1 = -19.69765 y x3 = -0.04613 en la
ecuación 2, se obtiene x2 = -3.42775; sustituyendo x1 =
-19.69765 y x2 = -3.42775 en la ecuación 3, se obtiene x3
= -0.05207. Por lo tanto, la segunda aproximación
es:

Ahora se pueden calcular los errores aproximados para
cada una de las incógnitas:

Puesto que no se ha cumplido el objetivo, se debe seguir
avanzando en el proceso iterativo. Se resumen los resultados de
esta manera:

Tercera iteración:

Cuarta iteración:

Así, el objetivo se ha logrado hasta la cuarta
iteración y se tiene que los valores aproximados de la
solución del sistema son:

CONCLUSIÓN

Luego de haber estudiado a profundidad estos temas o
herramientas
para resolver sistemas de ecuaciones, se concluye que para
resolver estos sistemas de ecuaciones lineales existen diferentes
métodos,
pero dependerá del gusto de cada persona elegir
uno en específico. Sin embargo, muchas veces la
elección no será arbitraria, pues cada
método tiene sus ventajas y sus desventajas. Algunos
métodos son más exactos, otros más
fáciles de programar, otros más cortos, etc. Para
ser capaces de elegir un método apropiado, lo primero que
se necesita es comprender cómo se desarrolla cada uno de
estos procesos.

Luego de la elaboración de este reporte, ya se
tiene una buena base y el
conocimiento de los temas para poder comenzar
a programar en la computadora
estos procesos. Como se mencionó en la introducción, los dos métodos
estudiados en este trabajo son
ideales para programarlos por computadora,
pues son iterativos y muy largos. Trabajar esto en papel
podría resultar extremadamente largo y tedioso. Por ello
son métodos ideales para trabajarlos en
computadora.

El aprendizaje
adquirido en esta investigación ha sido de gran valor y
seguramente servirá de la misma manera a aquellos quienes
posteriormente lean estas explicaciones y lo expuesto en este
reporte.

BIBLIOGRAFÍA

1. C. Chapra, S.; P. Canale, R. Métodos
   Numéricos para Ingenieros. (3ª ed.).
   McGrawHill.
2. Factorización LU. Wikipedia.
   Extraído el 22 Enero, 2007, de http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_LU
3. MÉTOTO DE GAUSS-SEIDEL. Universidad
   Autónoma de Ciudad Juárez (UACJ).
   Extraído el 22 Enero, 2007, de

Jaime Montoya

www.jaimemontoya.com

Santa Ana, 30 de noviembre de 2007

El Salvador